The invention related to a network technology for connecting operation elements.
A coarse grain reconfigurable circuit is configured by a plurality of processing elements (PEs) having a variety of functions and an internal connecting network that connects the PEs, and actualizes a data transfer between the arbitrary processing elements by changing connection information for setting paths of the internal connecting network. Herein, the “coarse grade” implies a reconfigurable circuit built up between the processing elements in which a basic instruction is operation on a word-by-word basis.
An ideal network is a network that can set an arbitrary data path and has a small number of circuits to be used and a small number of circuit stages of the path. And a variety of networks are proposed. The network in which the path exists for every output destination from an arbitrarily selected input source is classified into (1) a blocking network, wherein in the case of setting a certain path, this path setting hinders other paths, i.e., connections between the output destination and other input sources through other paths are blocked, and (2) a non-blocking network, wherein in the case of setting a certain path, this path setting does not hinder other paths, i.e., the connections through other paths are not blocked. In the reconfigurable circuit, signals are outputted simultaneously from a plurality of elements, and hence the non-blocking network is ideal in terms of the data transfer.
The non-blocking network, however, requires a great number of wirings, and therefore the circuit gets into a large scale. For example, an n-input/n-output network needs switches of n2 in a crossbar switch network.
FIG. 1 shows an example of 3-stage Clos network defined as one of the non-blocking networks. The 3-stage Clos network shown in FIG. 1 requires switches of 3n1.5. In FIG. 1, eight tuples of 8-input/8-output crossbar switch blocks are formed per stage, and thus the 8-tuple crossbar switch blocks are provided at three stages.
In this case, an input count (the number of inputs) n=64, and an output count (the number of inputs) n=64, and therefore n0.5=8. A switch count (the number of switches) of the one crossbar switch block is given by 8×8=n0.5×n0.5, and these crossbar switch blocks are provided by 3 stages×8 tuples=3×n0.5. Accordingly, to generalize FIG. 1, the switch count becomes 3n1.5.
Generally, in the blocking network, the circuit can be downsized, and, in typical networks such as an omega network and a baseline network, the circuit can be actualized on a circuit scale on the order of 2n·log(n), however, some paths that can not be actualized simultaneously occur because of there being some paths blocked by setting one path.                [Patent document 1] Japanese Examined Patent Publication No. 7-71353        [Patent document 2] Japanese Patent Publication No. 2786246        